1. Field of the Invention
The present invention relates to an adder, and more particularly to an adder that operates at a high speed.
2. Description of the Related Art
In recent years, computers are becoming faster and faster. Therefore, a higher speed arithmetic circuit is required and a technique for increasing an operating speed of an adder serving as an important part thereof becomes important. A large number of techniques for realizing a high speed adder have been known. Of those, a conditional sum adder has been widely known as one of the highest-speed adders. 
FIG. 1 is a circuit diagram showing a 4-bit conditional sum adder of a first conventional example described in, particularly, FIG. 6 in Kuo-Hsing Cheng et al., “The improvement of conditional sum adder for low power applications”, 1998. IEEE ASIC Conference Proceedings, pp. 131-134. As shown in FIG. 1, in the first conventional example, when a binary number (A_3), A_2, A_1, A_0) is added to a binary number (B_3, B_2, B_1, B_0), each of conditional cells 111 in a first circuit stage 21 generates both provisional bit sum signals and provisional carry signals and outputs them. Here, the provisional sums include a bit sum signal (for example, S0_1) with respect to the case where carry is produced from a low order bit and a bit sum signal (for example, S1_1) with respect to the case where no carry is produced. In addition, the provisional carries include a carry signal (for example, C0_1) with respect to the case where carry s produced from a low order bit and a carry signal (for example, C1_1) with respect to the case where no carry is produced. In a second circuit stage 22, one of the two provisional sums and one of the two provisional carries are selected by multiplexers (MUXs) 120 in accordance with a carry signal from a low order bit and transferred to a next stage. In a third circuit stage 23, actual bit sums S_0 to S_3 and an output carry signal Cout are generated by actual carry signals and outputted to the outside of the adder. According to to first conventional example, because the 2.sup.N-bit adder can be realized by (N+1) circuit stages, the high speed operation is possible. However, in the first conventional example, because the adder includes a large number of multiplexers and the number of wirings is large, power dissipation is large.
As an adder improved to reduce power dissipation, there is a conditional carry adder of a second conventional example described in, particularly, FIG. 7 in Kuo-Hsing Cheng et al., “The improvement of conditional sum adder for low power application”, 1998. IEEE ASIC Conference Proceedings, pp. 131-134. FIG. 2 is a circuit diagram of a 16-bit conditional carry adder. As shown in FIG. 2, in the second conventional example, each of conditional cells 101 (FIG. 4B is a circuit diagram) is different from the conditional cell 111 in the first conventional example. That is, each of the conditional cells 101 in a first circuit stage 31 generates an exclusive OR signal of two input bits (for example, S0_1) and provisional carries and outputs them. Here, the provisional carries are composed of a pair of signals which are a carry signal with respect to the case where carry is produced from a low order bit and a carry signal with respect to the case where no carry is produced. In a second circuit stage 32 to a fifth circuit stage 35, each carry signal to be sent to a next circuit stage is selected by a multiplexer (MUX) 120 and a carry selector 110 in accordance with a carry signal from a low order bit and transferred in succession. In a sixth circuit stage 36 including exclusive OR circuits 130, actual bit sums S_1 to S_15 are generated and outputted to the outside of the adder. According to the second conventional example, because only the provisional carries may be generated and outputted and no provisional sums are required, the number of multiplexers (one carry selector is counted as two multiplexers) can be reduced. Accordingly, power dissipation at the time of operation can be reduced.
However, when the 2N-bit adder is realized in the second conventional example, (N+2) circuit stages are required. In the case of comparison using a 16-bit adder, although the number of circuit stages is five in the first conventional example, the number of circuit stages is six in the second conventional example. Therefore, because the number of logic stages in a critical path is increased by one stage, it is disadvantageous to increase a circuit operation speed.